#include<stdio.h>
#include<iostream>
using namespace std;

//排序方法的分类：
//按数据存储介质：内部排序和外部排序
//按比较器个数：  串行排序和并行排序
//按主要操作：    比较排序和基数排序
//按辅助空间：    原地排序和非原地排序
//按稳定性：      稳定排序和非稳定性排序
//按自然性：      自然排序和非自然排序

//排序的稳定性只对结构类型数据排序 有意义 


//按排序依据原则  
//插入排序：直接插入排序、折半插入排序、希尔排序	
//交换排序：冒泡排序、快速排序
//选择排序：简单选择排序、堆排序
//归并排序：2-路归并排序
//基数排序 


//存储结构----记录序列以顺序表存储 
#define InfoType char
#define MAXSIZE 20   //设记录不超过20个
typedef int KeyType; //设关键字为整型量(int 型)
typedef struct{  //定义每个记录(数据元素)的结构  
	KeyType key; //关键字 
	InfoType otherinfo; //其它数据项 
} RedType; //Record Type 
typedef struct{ //定义顺序表的结构 
	RedType r[MAXSIZE + 1]; //存储顺序表的向量  //r[0]一般作为哨兵或缓冲区 
	int length; //顺序表的长度 
}SqList;


//8.2插入排序 
//基本思想： 
//  每一步将一个待排序的对象，按其关键码的大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止  
//基本操作：有序插入 
//顺序法定位插入位置----直接插入排序 
//二分法定位插入位置----二分插入排序 
//缩小增量多遍插入排序--- 希尔排序 


//直接插入排序--采用顺序查找法查找插入位置  
void InsertSort(SqList &L){
	int i, j;
	for(i = 2; i <= L.length; ++i){
		if(L.r[i].key < L.r[i-1].key){   //若"<", 需将L.r[i]插入有序子表 
			L.r[0] = L.r[i];  //复制为哨兵 
			for(j = i-1; L.r[0].key < L.r[j].key; --j){
				L.r[j+1] = L.r[j]; //记录后移 
			}
			L.r[j+1] = L.r[0]; //插入到正确位置 
 		}
	}
}

//折半插入排序：查找插入位置时采用折半查找法 
void BInsert(SqList &L){
	for(int i = 2; i < L.length; ++i){ //依次插入第2到第n个元素 
		
		L.r[0] = L.r[i];  //当前插入元素存到"哨兵"位置 
		int low = 1, high = i - 1; //采用二分查找法查找插入位置 
		while(low <= high){
			int mid = (low + high) / 2;
			if(L.r[0].key < L.r[mid].key) high = mid - 1;
			else low = mid + 1;
		} //循环结束, high+1 则为插入位置 
		
		for(int j = i-1; j >= high + 1; --j) L.r[j+1] = L.r[j]; //移动元素
		L.r[high+1] = L.r[0]; //插入到正确位置 
	
	}
}


//希尔排序 Donald.L.Shell  ---- 缩小增量，多遍插入排序 
//基本思想：先将整个待排记录序列分割成若干子序列, 分别进行直接插入排序, 
//			待整个序列中的记录"基本有序"时, 再对全体记录进行一次直接插入排序 
//(1)定义增量序列Dk
//(2)对每个Dk进行"Dk-间隔"插入排序(k = M, M-1, ...1) 

//希尔排序算法(其中某一趟的排序操作)如下:
void ShellInsert(SqList &L, int dk){
	//对顺序表L进行一趟增量为dk的shell排序, dk为步长因子  
	for(int i = dk + 1; i < L.length; ++i){
		if(L.r[i].key <L.r[i-dk].key){
			L.r[0] = L.r[i];
			int j;
			for(j = i-dk; j > 0 && (L.r[0].key < L.r[j].key); j = j - dk)
				L.r[j+dk] = L.r[j];
			L.r[j+dk] = L.r[0];
		}
	}
} 

//希尔排序算法(主程序)如下： 
void ShellSort(SqList &L, int dlta[], int t){ //dk值依次存在dlta[t]中 
	//按增量序列dlta[0,...,t-1]对顺序表L作希尔排序 
	for(int k = 0; k < t; ++k)
		ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 
	
}//ShellSort



int main(void){
	return 0;
}

